package 牛客算法篇; /**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-24
 * Time:21:53
 */

/**
 *
 牛客算法篇:BM8 链表中倒数最后k个结点
 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 如果该链表长度小于k，请返回一个长度为 0 的链表。
 数据范围：0≤n≤1050≤n≤105，0≤ai≤1090≤ai​≤109，0≤k≤1090≤k≤109
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
 其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
 示例1
 输入：
 {1,2,3,4,5},2
 返回值：
 {4,5}
 说明：
 返回倒数第2个节点4，系统会打印后面所有的节点来比较。
 */
public class FindKthToTail {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (pHead == null){
            return null;
        }
        ListNode output = pHead;
        ListNode cur = output;
        int count = 0;
        while (count < k &&cur != null){
            count++;
            cur = cur.next;
        }
        while (cur != null){
            cur = cur.next;
            output = output.next;
            count++;
        }
        if (k > count){
            return null;
        }
        return output;
    }
}
